{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Element Appearing More Than 25% In Sorted Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSpecialInteger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有序数组中出现次数超过25%的元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非递减的&nbsp;<strong>有序&nbsp;</strong>整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。</p>\n",
    "\n",
    "<p>请你找到并返回这个整数</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,2,6,6,6,6,7,10]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10^4</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [element-appearing-more-than-25-in-sorted-array](https://leetcode.cn/problems/element-appearing-more-than-25-in-sorted-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [element-appearing-more-than-25-in-sorted-array](https://leetcode.cn/problems/element-appearing-more-than-25-in-sorted-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,6,6,6,6,7,10]', '[1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        last = -1\n",
    "        cnt = 0\n",
    "        for num  in arr:\n",
    "            if num != last:\n",
    "                cnt = 0\n",
    "                last = num\n",
    "            cnt += 1\n",
    "            if cnt > len(arr) / 4:\n",
    "                return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        nums = [0]*100001\n",
    "        tar = len(arr) / 4\n",
    "        for i in arr:\n",
    "            nums[i] += 1\n",
    "            if nums[i] > tar:\n",
    "                return i\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\r\n",
    "        n = len(arr)\r\n",
    "        percent = n//4 + 1\r\n",
    "        target = 0\r\n",
    "        cnt = 1\r\n",
    "        last = arr[0]\r\n",
    "        for item in arr[1:]:\r\n",
    "            if item == last:\r\n",
    "                cnt+=1\r\n",
    "            else:\r\n",
    "                last = item\r\n",
    "                cnt = 1\r\n",
    "                continue\r\n",
    "            \r\n",
    "            if cnt >= percent:\r\n",
    "                break\r\n",
    "        \r\n",
    "        return last\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        ln = len(arr)\n",
    "        step = ln // 4 + 1\n",
    "        for i in range(ln - step + 1):\n",
    "            if arr[i] == arr[i + step - 1]:\n",
    "                return arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        res = {}\n",
    "        corps = set(arr)\n",
    "        for element in corps:\n",
    "            res[element] = 0\n",
    "\n",
    "        for element in arr:\n",
    "            res[element] +=1\n",
    "        \n",
    "        res = sorted(res.items(), key=lambda x:x[1], reverse=True)\n",
    "        return res[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        counts = {}\n",
    "        total = 0\n",
    "        arr_set = set(arr)\n",
    "        for i in arr_set:\n",
    "            count = arr.count(i)\n",
    "            counts[i] = count\n",
    "            total += count\n",
    "        for i in arr_set:\n",
    "            if counts[i] > total * 0.25:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        i = j = 0\n",
    "        target = len(arr)//4 \n",
    "        print(target)\n",
    "        while i < len(arr):\n",
    "            j = i\n",
    "            while True:\n",
    "                if j - i > target:\n",
    "                        return arr[i]\n",
    "                if arr[i] == arr[j]:\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i = j\n",
    "                    break\n",
    "                    \n",
    "                       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### 官2：二分\n",
    "# import bisect\n",
    "# class Solution:\n",
    "#     def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "#         n=len(arr)\n",
    "#         span=n//4+1\n",
    "#         for i in range(0,n,span):\n",
    "#             ll=bisect.bisect_left(arr,arr[i])\n",
    "#             rr=bisect.bisect_right(arr,arr[i])\n",
    "#             if rr-ll>=span:\n",
    "#                 return arr[i]\n",
    "#         return -1\n",
    "\n",
    "### 官1:遍历\n",
    "class Solution:\n",
    "    def findSpecialInteger(self,arr):\n",
    "        # cur,cnt=-1,0\n",
    "        cur,cnt=arr[0],0 ### 初始化的高级\n",
    "        n=len(arr)\n",
    "        for c in arr:\n",
    "            if cur==c:\n",
    "                cnt+=1\n",
    "                if 4*cnt>n:\n",
    "                    return c \n",
    "            else:\n",
    "                cur=c \n",
    "                cnt=1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        temp = [0]*(10**5+1)\n",
    "        for i in arr:\n",
    "            temp[i] += 1\n",
    "        return temp.index(max(temp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        if N < 4:\n",
    "            return arr[0]\n",
    "\n",
    "        threshold = N // 4\n",
    "        s = 0\n",
    "        for i in range(1, N):\n",
    "            if arr[i] == arr[i-1]:\n",
    "                if i-s+1 > threshold:\n",
    "                    return arr[i]\n",
    "            else:\n",
    "                s = i\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        cov = n // 4 \n",
    "        for i in range(n-cov):\n",
    "            if arr[i] == arr[i+cov]:\n",
    "                return arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        s=len(arr)\n",
    "        for i in range(s//2+1):\n",
    "            if s//arr.count(arr[i])<4:\n",
    "                return arr[i]\n",
    "            elif s//arr.count(arr[s-1-i])<4:\n",
    "                return arr[s-1-i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i == n or arr[i] != arr[i - 1]:\n",
    "                if (i - j) * 4 > n:\n",
    "                    return arr[j]\n",
    "                j = i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        ln = len(arr)\n",
    "        if ln == 1:\n",
    "            return arr[0]\n",
    "        c = 1\n",
    "        for i in range(ln - 1):\n",
    "            if arr[i + 1] == arr[i]:\n",
    "                c += 1\n",
    "            else:\n",
    "                c = 1\n",
    "            if c * 4 > ln:\n",
    "                return arr[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        cur=-1\n",
    "        cur_count=0\n",
    "        num=len(arr)\n",
    "        for n in arr:\n",
    "            if n==cur:\n",
    "                cur_count+=1\n",
    "            else:\n",
    "                cur=n\n",
    "                cur_count=1\n",
    "            if cur_count*4>num:\n",
    "                return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dis=n//4\n",
    "        i=0\n",
    "        j=i+dis\n",
    "        while j<n:\n",
    "            if arr[i]==arr[j]:\n",
    "                return arr[i]\n",
    "            i+=1\n",
    "            j+=1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        threshold = len(arr) * 0.25\n",
    "        currNum = -1\n",
    "        currCount = 0\n",
    "        for n in arr:\n",
    "            if n != currNum:\n",
    "                currNum = n\n",
    "                currCount = 1\n",
    "            else:\n",
    "                currCount += 1\n",
    "            if currCount > threshold:\n",
    "                return n\n",
    "        return currNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        span = n // 4 + 1\n",
    "        for i in range(0, n, span):\n",
    "            iter_l = bisect.bisect_left(arr, arr[i])\n",
    "            iter_r = bisect.bisect_right(arr, arr[i])\n",
    "            if iter_r - iter_l >= span:\n",
    "                return arr[i]\n",
    "        return -1\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/element-appearing-more-than-25-in-sorted-array/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        a=0\n",
    "        for i in range(len(arr)):\n",
    "            if arr.count(arr[i])/len(arr)>0.25:\n",
    "                a=arr[i]\n",
    "                break\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        span = n // 4 + 1\n",
    "        for i in range(0, n, span):\n",
    "            iter_l = bisect.bisect_left(arr, arr[i])\n",
    "            iter_r = bisect.bisect_right(arr, arr[i])\n",
    "            if iter_r - iter_l >= span:\n",
    "                return arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        span = n // 4 + 1\n",
    "        for i in range(0, n, span):\n",
    "            iter_l = bisect.bisect_left(arr, arr[i])\n",
    "            iter_r = bisect.bisect_right(arr, arr[i])\n",
    "            if iter_r - iter_l >= span:\n",
    "                return arr[i]\n",
    "        return -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        step = int(n/4)  # 向下取整，如9/4=2\n",
    "        for i in range(n - step):\n",
    "            if arr[i] == arr[i + step]:\n",
    "                return arr[i]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        if len(arr)==1:\n",
    "            return arr[0]\n",
    "        v=0\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i]!=arr[i-1]:\n",
    "                v=0\n",
    "            else:\n",
    "                v+=1\n",
    "            if v>=int(len(arr)/4):\n",
    "                return arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return arr[0]\n",
    "        c = 1\n",
    "        for i in range(len(arr) - 1):\n",
    "            if arr[i + 1] == arr[i]:\n",
    "                c += 1\n",
    "            else:\n",
    "                c = 1\n",
    "            if c * 4 > len(arr):\n",
    "                return arr[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        length = len(arr)\n",
    "        count = length // 4 + 1\n",
    "        for i in range(length - count + 1):\n",
    "            if arr[i] == arr[i+count-1]:\n",
    "                return arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "### 官2：二分\n",
    "import bisect\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        span=n//4+1\n",
    "        for i in range(0,n,span):\n",
    "            ll=bisect.bisect_left(arr,arr[i])\n",
    "            rr=bisect.bisect_right(arr,arr[i])\n",
    "            if rr-ll>=span:\n",
    "                return arr[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr) // 4\n",
    "        if arr.count(arr[-1]) >= n + 1:\n",
    "            return arr[-1]\n",
    "        res = [arr[0], arr[n], arr[2 * n], arr[3 * n]]\n",
    "\n",
    "        for i in res:\n",
    "            if arr.count(i) >= n + 1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        l = len(arr) // 4 + 1\n",
    "        for i in range(0, len(arr), l):\n",
    "            if bisect_right(arr, arr[i]) - bisect_left(arr, arr[i]) >= l:\n",
    "                return arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        cur, cnt = arr[0], 0\n",
    "        for i in range(n):\n",
    "            if arr[i] == cur:\n",
    "                cnt += 1\n",
    "                if cnt * 4 > n:\n",
    "                    return cur\n",
    "            else:\n",
    "                cur, cnt = arr[i], 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        return max(arr, key = arr.count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        # 和上一题：出现超过一半次数的元素不太一样: 已经有序了\n",
    "        # 用二分查找，达到O(logN)\n",
    "        # 1 2 3 4 5 6 7 8\n",
    "        # 1 1 2 2 3 4 4 4\n",
    "        n = len(arr)\n",
    "        \n",
    "        span = n // 4 + 1\n",
    "\n",
    "        for i in range(0, n, span): \n",
    "            iter_l = bisect.bisect_left(arr, arr[i])\n",
    "            iter_r = bisect.bisect_right(arr, arr[i])\n",
    "\n",
    "            if iter_r - iter_l >= span: \n",
    "                return arr[i]\n",
    "        return \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        span = n // 4 + 1\n",
    "        for i in range(0, n, span):\n",
    "            iter_l = bisect.bisect_left(arr, arr[i])\n",
    "            iter_r = bisect.bisect_right(arr, arr[i])\n",
    "            if iter_r - iter_l >= span:\n",
    "                return arr[i]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n, count = len(arr), 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] == arr[i - 1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                if count > n // 4:\n",
    "                    return arr[i - 1]\n",
    "                count = 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        target_count = n // 4\n",
    "\n",
    "        count = 1\n",
    "        current_element = arr[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if arr[i] == current_element:\n",
    "                count += 1\n",
    "            else:\n",
    "                current_element = arr[i]\n",
    "                count = 1\n",
    "\n",
    "            if count > target_count:\n",
    "                return current_element\n",
    "\n",
    "        return 1  # 如果没有找到满足条件的元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        count_dict={}\n",
    "        for i in arr:\n",
    "            if i not in count_dict:\n",
    "                count_dict[i] = 1\n",
    "            else:\n",
    "                count_dict[i] += 1\n",
    "            if count_dict[i]>0.25*len(arr):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        dict={}\n",
    "        n=len(arr)\n",
    "        for num in arr:\n",
    "            if num not in dict.keys():\n",
    "                dict[num]=1\n",
    "            else:\n",
    "                dict[num]+=1\n",
    "            if dict[num]>n*0.25:\n",
    "                return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return arr[0]\n",
    "        numDict = {}\n",
    "        for i in arr:\n",
    "            if i not in numDict.keys():\n",
    "                numDict[i] = 1\n",
    "            else:\n",
    "                numDict[i] += 1\n",
    "                if numDict[i] > (len(arr) // 4):\n",
    "                    return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr) // 4\n",
    "        if arr.count(arr[-1]) >= n + 1:\n",
    "            return arr[-1]\n",
    "        res = [arr[0], arr[n], arr[2 * n], arr[3 * n]]\n",
    "\n",
    "        for i in res:\n",
    "            if arr.count(i) >= n + 1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr) // 4\n",
    "        if arr.count(arr[-1]) >= n + 1:\n",
    "            return arr[-1]\n",
    "        res = [arr[-1], arr[n], arr[2 * n], arr[3 * n]]\n",
    "\n",
    "        for i in res:\n",
    "            if arr.count(i) >= n + 1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr) // 4\n",
    "        if arr.count(arr[-1]) >= n + 1:\n",
    "            return arr[-1]\n",
    "        res = [arr[0], arr[n], arr[2 * n], arr[3 * n]]\n",
    "\n",
    "        for i in res:\n",
    "            if arr.count(i) >= n + 1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr) // 4\n",
    "        if arr.count(arr[-1]) >= n + 1:\n",
    "            return arr[-1]\n",
    "        res = [arr[0], arr[n], arr[2 * n], arr[3 * n]]\n",
    "\n",
    "        for i in res:\n",
    "            if arr.count(i) >= n + 1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr) // 4\n",
    "        if arr.count(arr[-1]) >= n + 1:\n",
    "            return arr[-1]\n",
    "        res = [arr[0], arr[n], arr[2 * n], arr[3 * n]]\n",
    "\n",
    "        for i in res:\n",
    "            if arr.count(i) >= n + 1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        count = {}\n",
    "        for i in arr:\n",
    "            if i in count:\n",
    "                count[i] += 1\n",
    "            else:\n",
    "                count[i] = 1\n",
    "\n",
    "            if count[i] * 4 > n:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr) // 4\n",
    "     \n",
    "        res = [arr[-1], arr[n], arr[2 * n], arr[3 * n]]\n",
    "\n",
    "        for i in res:\n",
    "            if arr.count(i) >= n + 1:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        x = len(arr)//4+1\n",
    "        zd = dict()\n",
    "        for i in arr:\n",
    "            zd[i] = zd.get(i, 0) + 1\n",
    "            if zd[i] == x:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        target = len(arr)*0.25\n",
    "        dic = {}\n",
    "        for i in arr:\n",
    "            dic[i] = arr.count(i)\n",
    "            if dic[i] > target:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr) / 4\n",
    "        c = Counter()\n",
    "        for i in arr:\n",
    "            c[i] += 1\n",
    "            if c[i] > n:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        dict1={}\n",
    "        if len(arr)==1:\n",
    "            return arr[0]\n",
    "        for i in arr:\n",
    "            if i not in dict1.keys():\n",
    "                dict1[i]=1\n",
    "            else:\n",
    "                dict1[i]+=1\n",
    "                if dict1[i] > len(arr)//4:\n",
    "                    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        total=len(arr)\n",
    "        dict={}\n",
    "        for i in arr:\n",
    "            if not i in dict:\n",
    "                dict[i]=0\n",
    "            dict[i]+=1\n",
    "            if dict[i]/total>0.25:\n",
    "                return i\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        l=Counter(arr)\n",
    "        ans,m=0,0\n",
    "        for (i,j) in l.items():\n",
    "            if j>m:\n",
    "                m=j\n",
    "                ans=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        count = 1\n",
    "        res = []\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i]== arr[i-1]:\n",
    "                count += 1\n",
    "            elif count != 0:\n",
    "                res.append([count,arr[i-1]])\n",
    "                count = 1\n",
    "        if count != 0:\n",
    "            res.append([count,arr[-1]])\n",
    "        res = sorted(res,reverse = True)\n",
    "        return res[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "    d = dict()\n",
    "    n = len(arr)\n",
    "    for c in arr:\n",
    "      if c in d: d[c] +=1\n",
    "      else: d[c] = 1\n",
    "      if d[c] > n*0.25: return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        counter=collections.Counter(arr)\n",
    "        for i in counter.keys():\n",
    "            if counter[i]>len(arr)/4:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        for key, num in collections.Counter(arr).most_common(1):\n",
    "            return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        count = Counter(arr)\n",
    "        for i,j in count.items():\n",
    "            if j > n*0.25:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dict_num =Counter(arr)\n",
    "        \n",
    "        for key,value in dict_num.items():\n",
    "            if value >  n/4 :\n",
    "                return key\n",
    "        return -1\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        a=len(arr)\n",
    "        dic={}\n",
    "        for i in arr:\n",
    "            if i not in dic:\n",
    "                dic[i]=1\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "        for j in dic:\n",
    "            if dic[j]>a*0.25:\n",
    "                return j "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        arr_dic = {}\n",
    "        for number in arr:\n",
    "            if number not in arr_dic:\n",
    "                arr_dic[number] = 1\n",
    "            else:\n",
    "                arr_dic[number] += 1\n",
    "\n",
    "        for key,value in arr_dic.items():\n",
    "            if value > len(arr)*0.25:\n",
    "                return key\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dict_num =Counter(arr)\n",
    "        \n",
    "        for key,value in dict_num.items():\n",
    "            if value >  n/4 :\n",
    "                return key\n",
    "        return -1\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        cnt = Counter(arr)\n",
    "        m = max(cnt.values())\n",
    "        ans = [items for items ,value in cnt.items() if value == m]\n",
    "        return ans[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        dic = Counter(arr)\n",
    "        for k,v in dic.items():\n",
    "            if 4*v > len(arr):\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        return mode(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        ds,l = Counter(arr),len(arr)\n",
    "        for k,v in ds.items():\n",
    "            if v * 4 > l:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        \n",
    "        n = len(arr)//4\n",
    "\n",
    "        for x in set(arr):\n",
    "            if arr.count(x) > n:\n",
    "                return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        myset = set(arr)\n",
    "        for i in myset:\n",
    "            if arr.count(i) > len(arr)*0.25:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        return max(set(arr), key = arr.count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        lens = len(arr)\n",
    "        target = lens // 4\n",
    "        h = dict()\n",
    "        index = 0\n",
    "        for i in arr:\n",
    "            if i in h:\n",
    "                h[i] = h[i] + 1\n",
    "            else:\n",
    "                h[i] = 1\n",
    "\n",
    "        for k, v in h.items():\n",
    "            if v > target:\n",
    "                return k\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        list1=Counter(arr)\n",
    "        for key,val in list1.items():\n",
    "            if val /n >0.25:\n",
    "                return key\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        a = Counter(arr)\n",
    "        cnt, ans = 0, 0\n",
    "        for x in a:\n",
    "            if a[x] > cnt:\n",
    "                ans = x\n",
    "                cnt = a[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        count = Counter(arr)\n",
    "        for i,j in count.items():\n",
    "            if j > n*0.25:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dic = Counter(arr)\n",
    "        for k,v in dic.items():\n",
    "            if 4*v>n:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        s = Counter(arr)\n",
    "        n = len(arr)\n",
    "        for x, y in s.items():\n",
    "            if y >(n//4):\n",
    "                return x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        for k,v in Counter(arr).items():\n",
    "            if v/n>0.25:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        return collections.Counter(arr).most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSpecialInteger(self, arr: List[int]) -> int:\n",
    "        dic=Counter(arr)\n",
    "        n=len(arr)\n",
    "        for k,v in dic.items():\n",
    "            if v*4>n:\n",
    "                return k"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
